Міністерство Освіти України Національний університет «Львівська політехніка» Методичні вказівки До лабораторної роботи № 12 На тему: «Алгоритм побудови бінарного дерева згортання» з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» ЗАТВЕРДЖЕНО на засіданні кафедри програмного забезпечення протокол № від 2008 року місто Львів 2008 рік Методичні вказівки до лабораторної роботи з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» Укладачі: Семчишин Ю. Б. Коротєєва Т. О. Вовчак І. Г. Відповідальний за випуск: Рецензенти: Тема роботи: Алгоритм побудови бінарного дерева згортання Мета роботи: Вивчити та дослідити методи обробки даних. Ознайомитись із алгоритмом побудови бінарного дерева згортання. Виконати лабораторну роботу використавши здобуті знання з методів обробки даних, зокрема алгоритму побудови бінарного дерева згортання. ТЕОРЕТИЧНІ ВІДОМОСТІ Необхідно побудувати дерево згортання Т(Х, F) графу. Множина вершин Х графу належатимуть до 1-го рівня дерева згортання, приймемо Х1 = Х. На першому кроці в множині Х2 маємо групи з двох елементів, для яких функція критерію F приймає екстремальне значення. Утворені групи належать до множини 2-го рівня дерева згортання. На другому кроці формується множина Х3 3-го рівня з елементів множини Х1 і Х2 . Процес продовжується до утворення множини Хk , яка складається з одного елемента – кореня дерева згортання. Алгоритм А А1. Для всіх хi, хj є Х1 визначити функцію критеріюF(хi, хj); А2. Об‘єднати пари елементів хk, хt з найкращим значенням функції критерію F і виключити їх зі списку елементів – кандидатів на об‘єднання. Приклад роботи алгоритму побудови бінарного дерева згортання представлено на рис. 1.  SHAPE \* MERGEFORMAT 
d a b a a a e e c c b b f f e d c d adef abcde abcdef abcd abcd 2 2 3 3 2 2 2 2 2 2
 Рис. 1. Дерево згортання. РЕКОМЕНДОВАНІ ДЖЕРЕЛА http://studik.lviv.ua/index.php?option=com_content&task=view&id=47. Базилевич Р. П., Гудз І. Б., Ждан А. Р. Ієрархічна кластеризація складних схем // Вісник НУ «Львівська політехніка», № 546, «Комп'ютерні системи та мережі», НУЛП, 2005. — С. 3–7. 2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм побудови бінарного дерева згортання. Використовувати мову програмування C/C++. Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи. 3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ Отримати індивідуальне завдання у викладача; Уточнити завдання (можливі різні трактування завдання); Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу (алгоритму) на даній лабораторній роботі; Протестувати на наявність логічних помилок програми; Оформити звіт відповідно до стандарту; Захистити виконану роботу. 4. КОНТРОЛЬНІ ПИТАННЯ Які ви знаєте методи обробки даних? Який метод обробки даних був розглянений на даній лабораторній роботі? Від чого прямо – залежним являється швидкість побудови бінарного дерева згортання? Опишіть характеристики даного методу. Наскільки являється ефективним даний метод обробки даних? Чи використовують даний метод на практиці, і наскільки часто? Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах? Чим оригінальним виділяється даний метод від інших?